8.5 归并排序

归并排序也是一种分而治之的排序算法。它将数组分成两个子数组，分别对其进行排序，然后将两个已排序的子数组合并为一个有序的数组。

初步听起来好像与快速排序是一样的，但是其实还是有一些区别的。

快速排序随机选择一个元素作为基准，将数组分为两部分；归并排序是从中间平分。

快速排序不需要进行合并操作，快速排序在划分时已经完成了左右的排序，分割之后不再需要额外的合并操作；归并排序需要需要额外的合并步骤。

归并排序具有稳定的时间复杂度 O(n log n)，适用于大规模数据排序。

本节代码存放目录为 lesson22

概念与原理

归并排序的基本思想

• 分解：将数组递归地分成两个子数组，直到每个子数组的大小为1。

• 合并：将两个有序的子数组合并为一个有序的数组。

• 递归：不断对左右子数组进行递归，最后完成整个数组的排序。

归并排序的关键在于合并两个有序数组的过程，这一步确保了每次都能生成更大的有序序列，直到所有元素都被合并到一个有序数组中。

归并排序的步骤示例

给定如下无序数组，按照从小到大排序：

[5, 3, 8, 4, 2]

通过归并排序的步骤如下：

第一步：分解

- 将数组分为两个子数组：[5, 3, 8] 和 [4, 2]

- 继续分解：[5, 3, 8] -> [5, 3] 和 [8]；[4, 2] -> [4] 和 [2]

- 继续分解：[5, 3] -> [5] 和 [3]

第二步：合并

- 合并 [5] 和 [3]，得到 [3, 5]

- 合并 [3, 5] 和 [8]，得到 [3, 5, 8]

- 合并 [4] 和 [2]，得到 [2, 4]

第三步：合并整个数组

- 合并 [3, 5, 8] 和 [2, 4]，得到最终的排序结果 [2, 3, 4, 5, 8]

最终，排序结果为 [2, 3, 4, 5, 8]。

归并排序的时间复杂度

归并排序每次将数组分为两个子数组，递归处理每个子数组，因此其时间复杂度如下：

• 最坏情况：O(n log n)，无论数组初始状态如何，归并排序的时间复杂度始终为 O(n log n)。

• 最好情况：O(n log n)，同样，归并排序的最好情况也是 O(n log n)。

• 平均情况：O(n log n)，归并排序的平均情况表现非常稳定。

归并排序的空间复杂度为 O(n)，因为需要额外的数组空间来存储合并后的子数组。

Go语言的实现

实现代码如下：

// merge 函数用于合并两个有序数组
func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0

    // 比较左右两部分的元素，将较小的加入结果数组
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // 将剩余的元素加入结果数组
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)

    return result
}

// mergeSort 实现归并排序
func mergeSort(arr []int) []int {
    // 如果数组长度小于2，直接返回
    if len(arr) < 2 {
        return arr
    }

    // 分解数组
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])

    // 合并两个有序子数组
    return merge(left, right)
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    sortedArr := mergeSort(arr)
    fmt.Println("最终排序结果: ", sortedArr)
}

执行结果如下所示：

最终排序结果:  [2 3 4 5 8]

通过上述代码，归并排序实现了对无序数组的排序过程。分解数组和合并两个有序数组是归并排序的核心步骤。

小结

本节我们讲解了归并排序的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：归并排序的时间复杂度为 O(n log n)，无论数组的初始状态如何，始终保持较好的性能。

• 稳定性：归并排序是稳定的排序算法。

• 应用场景：归并排序适用于大规模数据的排序，尤其在需要保证稳定性的场景中表现出色。